package com.example.origin.demo.suanfa.leecode;


public class No42JieShuiWei {
    /**
     * 给定一个非负整数数组 heights，它表示一个地形，数组中的每个数字代表每个位置的柱子高度。
     * 想象一下下雨时，雨水会在地形上汇集，你必须计算在这种情况下能够捕获到的雨水总量。
     * heights = [0,1,0,2,1,0,1,3,2,1,2,1]
     * @param args
     */
    public static void main(String[] args) {
        int[] arr = {0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1};
        int trap = trap(arr);
        System.out.println(trap);

        int[] arr2 = {4, 2, 0, 7, 2, 5};
        trap = trap(arr2);
        System.out.println(trap);


        int[] arr3 = {4, 2, 0, 7, 2, 5};
        trap = trap4(arr3);
        System.out.println(trap);
    }


    public static int trap3(int[] height) {
        int sum = 0;
        //最两端的列不用考虑，因为一定不会有水。所以下标从 1 到 length - 2
        for (int i = 1; i < height.length - 1; i++) {
            int max_left = 0;
            //找出左边最高
            for (int j = i - 1; j >= 0; j--) {
                if (height[j] > max_left) {
                    max_left = height[j];
                }
            }
            int max_right = 0;
            //找出右边最高
            for (int j = i + 1; j < height.length; j++) {
                if (height[j] > max_right) {
                    max_right = height[j];
                }
            }
            //找出两端较小的
            int min = Math.min(max_left, max_right);
            //只有较小的一段大于当前列的高度才会有水，其他情况不会有水
            if (min > height[i]) {
                sum = sum + (min - height[i]);
            }
        }
        return sum;
    }


    public static int trap2(int[] height) {
        int sum = 0;
        int[] max_left = new int[height.length];
        int[] max_right = new int[height.length];

        for (int i = 1; i < height.length; i++) {
            max_left[i] = Math.max(max_left[i - 1], height[i - 1]);
        }
        for (int i = height.length - 2; i >= 0; i--) {
            max_right[i] = Math.max(max_right[i + 1], height[i + 1]);
        }
        for (int i = 1; i < height.length - 1; i++) {
            int min = Math.min(max_left[i], max_right[i]);
            if (min > height[i]) {
                sum = sum + (min - height[i]);
            }
        }
        return sum;
    }


    private static int trap(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }

        int left = 0, right = heights.length - 1;
        int maxLeft = 0, maxRight = 0;
        int trappedWater = 0;

        while (left < right) {
            if (heights[left] < heights[right]) {
                if (heights[left] > maxLeft) {
                    maxLeft = heights[left];
                } else {
                    trappedWater += maxLeft - heights[left];
                }
                left++;
            } else {
                if (heights[right] > maxRight) {
                    maxRight = heights[right];
                } else {
                    trappedWater += maxRight - heights[right];
                }
                right--;
            }
        }

        return trappedWater;
    }

    private static int trap4(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        int sum = 0, left = 0, right = heights.length - 1, maxLeft = 0, maxRight = 0;
        while (left < right) {
            if (heights[left] < heights[right]) {
                if (heights[left] > maxLeft) {
                    maxLeft = heights[left];
                } else {
                    sum += (maxLeft - heights[left]);
                }
                left++;
            } else {
                if (heights[right] > maxRight) {
                    maxRight = heights[right];
                } else {
                    sum += (maxRight - heights[right]);
                }
                right--;
            }
        }
        return sum;
    }


}
